1. Field of the Invention
The present invention relates to a cryptographic device, and particularly to a cryptographic device having tamper resistance for preventing power analysis attacks on processors executing the RSA cryptosystem and the elliptic-curve cryptosystem.
2. Description of the Related Arts
Services using networks, such as electronic money, electronic tickets, services provided by e-government, have been widely employed. In these services, smart cards (IC cards) each including an IC chip storing secret information on a user are sometimes used in order to certify that the user is a legitimate user. Smart cards have functions that perform encryption, digital signatures, verification, and the like, and use users' secret information as keys. Smart cards present much better protection and tamper resistance against unauthorized accesses by third parties than magnetic cards because, in smart cards, the secret information is stored in the IC chips or memory units.
Examples of the cryptosystem employed in cryptographic devices such as smart cards include public key cryptosystem and common key cryptosystem. In public key cryptosystem, different keys are used for encryption and decryption. Typically, the key used for encryption (public key) is in a public state, and a person who wants to transmit his or her information encrypts the plaintext by using this public key before the transmission. The key used for decrypting the encrypted text (secret key) is held as secret information that is known only to the receiving person, and the receiving person can obtain the plaintext by decrypting the encrypted text with the secret key. Examples of public key cryptosystem include RSA cryptosystem and elliptic-curve cryptosystem.
One of the functions for performing the main operations that are required for executing the RSA cryptosystem is the modular exponentiation operation function. The exponentiation operation is an operation in the form ofa^d(mod n)=a×a× . . . ×a(d times)(mod n)where “^” represents the exponentiation, and a, d, and n represent integers. Also, “mod n” represents the remainder left after division by n. The functions of the RSA cryptosystem include encryption, decryption, signature generation, and signature verification. In decryption and signature generation, values related to the secret information of users are used for “d”.
Examples of functions for performing the main operations required for executing the processes of elliptic-curve cryptosystem include scalar multiplication. The scalar multiplication used herein is an operation in the form ofd×P=P+P+ . . . +P(d times)where d represents an integer and P represents a point on an elliptic curve. The functions based on elliptic-curve cryptosystem include encryption, decryption, signature generation, signature verification, and key sharing. In decryption, signature generation, and key sharing, values related to the secret information of users are used for “d”. The above modular exponentiation operation for the RSA cryptosystem and scalar multiplication for the elliptic-curve cryptosystem are examples for operations called the exponentiation operation.
Examples of techniques employed in the field of handling secret information include a technique called cryptanalysis (tampering technique). Cryptanalysis is a technique used for detecting what is included in secret information (such as a secret key) on the basis of available information (such as an encrypted text), the various methods of which are known. Among these methods, there is a method called side channel attack that has recently gained interest.
The side channel attack method is a cryptanalysis method that was introduced by P. Kocher in 1996 (see “Timing attacks on implementation of Diffie-Hellman, RSA, USA and other systems”, CRYPTO'96, Lecture Notes in Computer Science Vol. 1109, pp. 104-113, Springer-Verlag, 1996 (document [Koc96]). In this method, side channel information (electrical power consumption data, time consumption data, electromagnetic wave data and the like) obtained when various data are input into the cryptographic processor mounted on a smart card or the like is collected and analyzed in order to detect the key information in the cryptographic processor. It has been pointed out that, by using the side channel attack, the secret keys in cryptographic processors can be detected both in public key cryptosystem and common key cryptosystem.
An example of a method of side channel attack is a powerful method called power analysis attack, in which electric power consumption data is used. Examples of power analysis attacks include differential power analysis (DPA), reported by P. Kocher, J. Jaffe and B. Jun in Crypto'99, Lecture Notes in Computer Science Vol. 1666, pp. 388-397, Springer-Verlag, 1999 (document [KJJ99]), and simple power analysis (SPA). SPA is a method in which secret keys are detected on the basis of characteristics in electric power consumption data in cryptographic processors, and DPA is a method in which secret keys are detected by analyzing the differences between a large number of pieces of electric power consumption data. Other examples of power analysis attacks include the refined power analysis (RPA) reported by L. Goubin in “Refined Power-analysis Attacks on Elliptic Curve Cryptosystems”, PKC 2003, Lecture Notes in Computer Science Vol. 2567, pp. 199-210, Springer-Verlag, 2003 (document [Gou03]), and zero-value power analysis (ZVA) reported by T. Akishita and T. Takagi in “Zero-value Point Attacks on Elliptic Curve Cryptosystems”, ISC 2003, Lecture Notes in Computer Science Vol. 2851, pp. 218-233, Springer-Verlag, 2003 (document [AT03]).
The need for techniques that prevent such power analysis attacks as described above has been suggested in the field of international standardization. For example, in the protection profile (PP) for smart cards that is based on (ISO) (International Standards Organization) 15408 in the field of security, countermeasures against power analysis attacks are required. Also, in FIPS140-2, which is one of the standards for cryptographic modules employed in the USA, it is thought that countermeasures against power analysis attacks will be required in the future, although this need is only being discussed at present.
In RSA cryptosystem and elliptic-curve cryptosystems, the main operation in the cryptographic process is the exponentiation operation. Also, this exponentiation operation is the target of power analysis attacks. Hereinafter, a method of realizing the scalar multiplication d×P in elliptic-curve cryptosystem is described.
The binary method is an operation for computing the scalar multiplication. Some of the binary methods are a method in which computations are performed from the least significant bit (binary method (LSB)), a method in which computations are performed from the most significant bit (binary method (MSB), and a method that is a variation of the binary method (MSB) using the Montgomery chain (Montgomery method).
An example of an algorithm for the binary method (LSB) is given as (1) Algorithm 1, an example of an algorithm for the binary method (MSB) is given as (2) Algorithm 2, and an example of an algorithm for the Montgomery method is given as (3) Algorithm 3. In these algorithms, unless otherwise noted, lowercase letters (such as “d”) represent scalar values and capital letters (such as “P”) represent points on elliptic curves. Also, “^” represents exponentiation, and a series of numbers expressed between “(” and “)2” represents a number expressed as a binary number. Also, numbers preceded by an “S” (e.g., “S1:”) are step numbers in an exemplary program. Hereinafter, the four arithmetical operations on an elliptic curve are respectively included between “┌” and “┘”.
(1) Algorithm 1 [Binary method (LSB)]S1: T[0]    0, T[1]    PS2: for i = 0 upto n−1 {S3:if (d[i] == 1 ) {S4:T[0]    ┌T[0] + T[1]┘   *S5:}S6:T[1]   ┌2*T[1]┘S7: }S8: return T[0] ,where T[0], T[1], and T[2] represent temporary variables, d represents a scalar value in n bits, and d[i] represents a value of the lower i-th bit of d.
As an example, a case is described here in which the scalar multiplication ┌d×P┘ for d=21=2^4+2^2+2^0=(10101)2 (d is an integer in 5 bits) is performed. In step S1, the variable T[0] is set to the point 0, and the variable T[1] is set to the point P. In steps S2 through S7 that follow, respective processes corresponding to i=0, 1, 2, 3, 4 are executed.
When i=0, d[i]=d[0]=1, and accordingly the variable T[0] is set to ┌T[0]+T[1]┘ and the value of the variable T[0] after processing is P. In step S6, the variable T[1] is set to ┌2*T[1] and the variable T[1] after processing is ┌2×P┘.
When i=1, d[i]=d[1]=0, and accordingly steps S3 through S5 are skipped. In step S6, the variable T[1] is set to ┌2*T[1]┘, and the value of the variable T[1] after processing is ┌4×P┘.
When i=2, d[i]=d[2]=1, and accordingly in step S4 the variable T[0] is set to ┌T[0]+T[1]┘, and the value of the variable T[0 after processing is ┌5×P┘. In step S6, the variable T1] is set to ┌2*T[1]┘, and the value of the variable T[1] after processing is ┌8×P┘.
When i=3, d[i]=d[3]=0, and accordingly steps S3 through S5 are skipped. In step S6, the variable T[1] is set to ┌2*T[1]┘, and the value of the variable T[1] after processing is ┌16×P┘.
When i=4, d[i]=d[0]=1, and accordingly in step S4 the variable T[0] is set to ┌T[0]+t[1]┘ and the value of the variable T[0] after processing is ┌21×P┘. In step S6, the variable T[1] is set to ┌2*T[1]┘, and the value of the variable T[1] after processing is ┌32×P┘.
After the above processes, the processes in steps S2 through S7 are terminated, and the value of the variable T[0] i.e., ┌21×P┘, is output in the last step S8.
(2) Algorithm 2 [binary method (MSB)]S1: T[0]    PS2: for i = n−2 downto 0 {S3:T[0]    ┌2*T[0]┘S4:if ( d[i] == 1 ) {S5:T[0]    ┌T[0] + P┘    *S6:}S7: }S8: return T[0]where T[0] represents a temporary variable, d represents a scalar value in n bits, and d[i] represents a value of the lower i-th bit of d.
As an example, a case is described in which the scalar multiplication ┌d×P┘ for d=21=2^4+2^2+2^0=(10101)2 (d is an integer in 5 bits) is performed. In step S1, the variable T[0] is set to the point P. In steps S2 through S7 that follow, respective processes corresponding to i=3, 2, 1, 0 are executed.
When i=3, in step S3, the variable T[0] is set to ┌2*T[0]┘, and the value of the variable T[0] after processing is ┌2×P┘. Also, when i=3, d [i]=d[3]=0, and accordingly steps S4 through S6 are skipped.
When i=2, in step S3, the variable T[0] is set to ┌2*T[0]┘, and the value of the variable T[0] after processing is ┌4×P┘. Also, when i=2, d[i]=d[2]=1, and accordingly in step s5 the variable T[0] is set to ┌T[0]+P┘, and the value of the variable T[0] after processing is ┌5×P┘.
When i=1, in step S3, the variable T[0] is set to ┌2*T[0]┘, and the value of the variable T[0] after processing is ┌10×P┘. Also, when i=1, d [i]=d[1]=0, and accordingly steps S4 through s6 are skipped.
When i=0, in step S3, the variable T[0] is set to ┌2*T[0]┘, and the value of the variable T[0] after processing is ┌20×P┘. Also, when i=0, d[i]=d[0]=1, and accordingly variable T[0] is set to ┌T[0]+P┘ in step s5, and the value of the variable T[0] after processing is ┌21×P┘.
After the above processes, the processes in steps S2 through S7 are terminated, and the value of the variable T[0], i.e., ┌21×P┘ is output in the last step, S8.
(3) Algorithm 3 [Montgomery method]S1: T[0]    P, T[1]    ┌2*P┘S2: for i = n−2 downto 0 {S3:T[2]    ┌2*T[d[i]]┘S4:T[1]    ┌T[0] + T[1]┘S5:T[0]    T[2-d[i] ]S6:T[1]    T[1+d[i] ]S7: }S8: return T[0] ,where T[0], T[1], and T[2] represent temporary variables, d represents a scalar value in n bits, and d[i] represents a value of the lower i-th bit of d.
As an example, the case is described here in which the scalar multiplication ┌d×P┘ for d=21=2^4+2^2+2^0=(10101)2 (d is an integer in 5 bits) is performed. In step S1, the variable T[0] is set to the point P, and the variable T[1] is set to ┌2×P┘. In the following steps S2 through S7, respective processes corresponding to i=3, 2, 1, 0 are executed.
When i=3, d[i]=d[3]=0. In step S3, the variable T[2] is set to ┌2*T[0]┘, and the value of the variable T[2] after processing is ┌2×P┘. In step S4, the variable T[1] is set to ┌T[0]+T[1]┘, and the value of the variable T[1] after processing is ┌3×P┘. In step S5, the variable T[0] is set to T[2], and the value of the variable T[0] after processing is ┌2×P┘. In step S6, the variable T[1] is set to T[1], and the value of the variable T[1] is ┌3×P┘.
When i=2, d[i]=d[2]=1. In step S3, the variable t[2] is set to ┌2*T[1]┘, and the value of the variable T[2] after processing is ┌4×P┘. In step S4, the variable T[1] is set to ┌T[0]+T[1]┘, and the value of the variable T[1] after processing is ┌6×P┘. In step S5, the variable T[0] is set to T[1], and the value of the variable T[0] after processing is ┌6×P┘. In step s6, the variable T[1] is set to T[2], and the value of the variable T[1] after processing is ┌6×P┘.
When i=1, d[i]=d[1]=0. In step S3, the variable T[2] is set to ┌2*t[0]┘, and the value of the variable T[2] after processing is ┌10×P┘. In step S4, the variable T[1] is set to ┌T[0]+T[1]┘, and the value of the variable t[1] after processing is ┌11×P┘. In step S5, the variable T[0] is set to T[2], and the value of the variable T[0] after processing is ┌10×P┘. In step S6, the variable T[1] is set to T[1], and the value of the variable T[1] after processing is ┌11×P┘.
When i=0, d[i]=d[0]=0. In step S3, the variable T[2] is set to ┌2*T[1]┘, and the value of the variable T[2] after processing is ┌22×P┘. In step S4, the variable T[1] is set to ┌T[0]+T[1]┘, and the value of the variable T[1] after processing is ┌21×P┘. In step s5, the variable T[0] is set to T[1], and the value of the variable T[0] after processing is ┌21×P┘. In step S6, the variable T[1] is set to T[2], and the value of the variable T[1] after processing is ┌22×P┘.
After the above processes, the processes in steps S2 through S7 are terminated, and the value ┌21×P┘ of the variable T[0] is output in the last step, S8.
Also, in addition to the above binary methods (Algorithms 1 and 2) and the Montgomery method (Algorithm 3), a method called the window method can be employed for realizing the scalar multiplication ┌d×P┘. In the window method, using a width of, for example, 4-bit, scalar multiplication by integers 0 through 15 are computed as an initial process, the results are held in a table, and in a scalar multiplication by d, the scalar d is divided for every 4 bits (windows); thereby, the scalar multiplication is computed. Hereinafter, an example of an algorithm for the window method (4-bit width) is described as Algorithm 4.
(4) Algorithm 4 [Window method (4-bit width)]S01: W[0]    O, W[1]    PS02: for i = 2 upto 15 {S03:W[i] = ┌W[i-1] + P┘S04: }S05: T[0]    W[d[n−1,n−4] ]S06: for i = n−5 downto 3 step −4 {S07:T[0]    ┌16*T[0]┘S08:T[0]    ┌T[0] + W[d[i,i−3]]┘S09: }S10: return T[0] ,where it is assumed that d is a scalar value in n bits, and n is a multiple of 4. Also, it is assumed that d[i, i−3] is a value in 4-bits starting from the lower i-th bit to the (i−3)th bit of d. W[i] is a table used in the window method.
As an example, a case is described herein which the scalar multiplication for d=21=2^4+2^2+2^0=(10101)2=(0001 0101)2 (d is an integer in 5 bits) is computed. Because the bit length of d (i.e., 5) is not a multiple of 4, zeros are padded into the higher three bits and it is handled as 8 bits for convenience, which results in n=8. First, W[0]=0 and W[1]=P are set as the initial values in step S01. Next, steps S02 through S04 are executed for i=2, 3, . . . , 15. For each i, W[i]=┌W[i−1]+P┘ is set in step S03. Then, the value to which W[i] is set is ┌i×P┘. After the processes of steps S02 through S04, the variable T[0] is set to W[d[n−1, n−4]]=W[d[7, 4]]=W[0001]=┌1×P┘ in step S05.
Next, processes in steps S06 through S09 corresponding to i=3 are executed. In step S07, the process of T[0]←┌16*T[0]┘ is executed, and ┌16×P┘ is registered as the variable T[0]. In step S08, the process of T[0]←┌T[0]+W[d[i, i−3]]┘=┌T[0]+W[0101]┘=┌┌16×P┘+┌5×P┘┘=┌21×P┘, and ┌21×P┘ is registered as the variable T[0].
After the above processes, the processes in steps S06 through S09 are terminated. The value of ┌21×P┘ is output in the last step S10. In the window method, as described above, the scalar multiplication ┌d×P┘ is computed by using a table that is prepared in advance.
In a case in which the scalar multiplication is computed by using Algorithms 1 and 2 above, it depends on the bit value d[i] of d whether or not the processes in the steps with the marks of “*” are executed. In the simple power analysis (SPA), the secret key d is estimated by using this feature. From many experiments, it is detected that the waveform of power consumption that results from the addition of points on an elliptic curve (elliptic addition) and the waveform that results from doubling (elliptic doubling) can easily be distinguished from each other. Accordingly, it is possible to obtain the secret key d because the order and the number of elliptic additions and elliptic doublings can be obtained by measuring the waveforms formed in the computations in Algorithms 1 and 2 in processors. Additionally, Algorithms 3 and 4 do not include a branch condition that depends on the bit value d[i], and thus they have resistance to the SPA.
As a countermeasure against the SPA targeting Algorithms 1 and 2, a method called add-and-double-always method has been reported. In this method, an addition and a doubling are always computed for each bit in the algorithms. This method is reported by J. Coron, in “Resistance against Differential Power Analysis”, Cryptographic Hardware and Embedded Systems 1999 (CHES 1999), Lecture Notes in Computer Science Vol. 1717, pp. 292-302, Springer-Verlag, 1999 (document [Coron99]). Because the elliptic addition and elliptic doubling are always performed alternately in this method, this method is thought to have resistance to the SPA. Algorithm examples in which add-and-double-always method is performed on the above Algorithms 1 and 2 are given below as (5) Algorithm 1′ and (6) Algorithm 2′.
(5) Algorithm 1′ [Binary method (LSB, add-and-double-always)]S1: T[0]    0, T[2]    PS2: for i = 0 upto n−1 {S3:T[1]    ┌T[0] + T[2]┘S4:T[2]    ┌2*T[2]┘S5:T[0]    T[d[i]]S6: }S7: return T[0] ,where T[0], T[1], and T[2] represent temporary variables, d represents a scalar value in n bits, and d[i] represents a value of the lower i-th bit.
(6) Algorithm 2′ [Binary method (MSB, add-and-double-always)]S1: T[0]    0, T[2]    PS2: for i = n−1 downto 0 {S3: T[0]    ┌2*T[0]┘S4: T[1]    ┌T[0] + T[2]┘S5: T[0]    T[d[i]]S6: }S7: return T[0] ,where T[0], T[1], and T[2] represent temporary variables, d represents a scalar value in n bits, and d[i] represents a value of the lower i-th bit.
By using Algorithms 1′, 2′, 3, and 4 above, it is possible to prevent the SPA. However, the document [Coron99] describes the DPA targeting these algorithms, and points out that a secret key is analyzed by the DPA even when these algorithms are used. Also, the analysis methods using the RPA and the ZVA are reported.
Neither the binary methods nor the Montgomery method have resistance to SPA, DPA, RPA, or ZVA. The exponent splitting (ES) method, a countermeasure against these power analysis methods, is reported by C. Clavier, M. Joye, in “Universal Exponentiation Algorithm—A First Step towards Provable SPA-resistance—”, Cryptographic Hardware and Embedded Systems 2001 (CHES 2001), Lecture Notes in Computer Science Vol. 2162, pp. 300-308, Springer-Verlag, 2001 (document [Clavier-Joye01]). This ES method is a method in which scalar values are converted at random, the scalar d is divided into d=r+(d−r) by the random number r, and two scalar multiplications ┌r×P┘ and ┌(d−r)×P┘ are computed independently; thereafter, a scalar multiplication ┌d×P┘ is computed by adding the results of the two scalar multiplications to each other, which is based on a below equation.┌┌r×P┘+┌(d−r)×P┘┘=┌d×P┘
In the ES countermeasure, an algorithm having resistance to other types of SPA/DPA is used for the above two scalar multiplications ┌r×P┘ and ┌(d−r)×P┘.
(7) Algorithm 5 [Exponent Splitting method]S1: r    random( )S2: T[1]    scalar(r, P)S3: T[2]    scalar(d-r, P)S4: T[0]    ┌T[1] + T[2]┘S5: return T[0] ,where random( ) represents a function for generating random numbers. Also, scalar (d, P) represents a function for computing the scalar multiplication ┌d×P┘, and is computed by using the above Algorithms 1′, 2′, 3, 4, and the like. Also, the variables r, T[0], T[1], T[2] represent temporary variables.
It is likely to say that the ES method has resistance to all of the types of SPA, DPA, RPA, and ZVA; however, a problem with this method in relation to the computational efficiency is the large amount of overhead that is required.
Patent Document 1 discloses an operating method, in which the elliptic addition and elliptic doubling are defined as one operation, and operations having the same properties are performed in parallel; thereby, resistance to side channel attacks is attained and scalar multiplication can be performed at a high speed.
Patent Document 1:
Japanese Patent Application Publication No. 2004-53814